We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the $\ell_2$ setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time.

We study differentially private stochastic optimization in convex and non-convex settings. For the convex case, we focus on the family of non-smooth generalized linear losses (GLLs). Our algorithm for the \ell_2 setting achieves optimal excess population risk in near-linear time, while the best known differentially private algorithms for general convex losses run in super-linear time. In the differentially private non-convex setting, we provide several new algorithms for approximating stationary points of the population risk. We also extend all our results above for the non-convex \ell_2 setting to the \ell_p setting, where 1 p \leq 2, with only polylogarithmic (in the dimension) overhead in the rates.